package 二分.二分答案;

import 蓝桥杯十二.I;

import java.util.Arrays;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/2/5 14:54
 */
public class leetcode打家劫舍4 {



    /*
    下面的 链接  : 灵神 还记录 相关 的类似的 题目!
    https://leetcode.cn/problems/house-robber-iv/solutions/2093952/er-fen-da-an-dp-by-endlesscheng-m558/
     最优解是 二分 答案 :

     最重要的 还是 ** 单调性  **

     这个 题 搞明之后 , 把上面的 链接上面的 题, 以及  **四边形不等式** 的那几个  **最化最值** 的问题
     给弄明白!
     顺便 再 看下 灵神的   ** 二分  和 回溯 ** 相关 模板的 讲解!

     */


    // 内存 溢出!
    public int solution(int k, int nums[]) {
        int dp[][] = new int[nums.length + 1][k + 1];
        return recursion(0, k, nums, dp);
    }

    public int recursion(int index, int k, int nums[], int dp[][]) {
        if (index >= nums.length) {
            return k == 0 ? 0 : Integer.MAX_VALUE;
        }
        // 判断 k <= 0 的这个 basecase
        if (dp[index][k] != 0) {
            return dp[index][k];
        }
        // choose current
        int ans1 = 0, ans2 = 0;
        ans1 = Math.max(recursion(index + 2, k - 1, nums, dp), nums[index]);
        // no choose
        ans2 = recursion(index + 1, k, nums, dp);

        return dp[index][k] = Math.min(ans1, ans2);
    }


    /*
    这个题，确实有点小酷

    f(index) : 表示的含义是， 从 index ~ len ，不能选择相邻元素，且在能力为 capicity 的时候，最多能够选择多少个元素 （且 nums[index] <= capicity 的时候才能选择）
     */

    public int solve(int index, int capicity, int nums[]) {
        if (index >= nums.length) {
            return 0;
        }
        int ans1 = 0, ans2 = 0;
        // no choose
        ans1 = solve(index + 1, capicity, nums);

        if (nums[index] <= capicity) {
            ans2 = solve(index + 2, capicity, nums) + 1;
        }

        return Math.max(ans1, ans2);
    }

    public int minCapability(int nums[],int k){
        // 尽量精准的找到答案的范围
        int max = Arrays.stream(nums).max().getAsInt();
        int min = Arrays.stream(nums).min().getAsInt();
        int l = min, r = max;
        while(l < r){
            int mid = l + r >> 1;
            if(dp(nums,mid) < k){
                l = mid + 1;
            }else{
                r = mid;
            }
        }
        return l;
    }


    public int dp(int nums[], int cap) {
        int dp[] = new int[nums.length + 1];
        dp[nums.length - 1] = nums[nums.length - 1] <= cap ? 1 : 0;
        for (int i = nums.length - 2; i >= 0; i--) {
            dp[i] = dp[i + 1];
            if (nums[i] <= cap) {
                dp[i] = Math.max(dp[i], dp[i + 2] + 1);
            }
        }
        return dp[0];
    }



    /*
     问题转化成了 给定一个 C 求， 找到 <= c的 元素  最多能 能窃取不相邻的房屋多少个!
     */

}
